// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"bytes"
	"cmd/internal/src"
	"fmt"
	"hash/crc32"
	"internal/buildcfg"
	"log"
	"math/rand"
	"os"
	"regexp"
	"runtime"
	"sort"
	"strings"
	"time"
)

// Compile是这个包的主要入口点。
// Compile修改f，以便在返回时：
// ·f中的所有值都映射到目标体系结构的0或1汇编指令
// ·f.块的顺序是发射块的顺序
// ·b.值的顺序是每个块中发出值的顺序
// ·f有一个非零regAlloc字段
func Compile(f *Func) {
	// TODO:调试-设置标志以控制编译器的详细程度，
	// 在之前/之后转储IR的阶段等。
	if f.Log() {
		f.Logf("compiling %s\n", f.Name)
	}

	var rnd *rand.Rand
	if checkEnabled {
		seed := int64(crc32.ChecksumIEEE(([]byte)(f.Name))) ^ int64(checkRandSeed)
		rnd = rand.New(rand.NewSource(seed))
	}

	// 如果发生死机，则钩住打印功能和阶段
	phaseName := "init"
	defer func() {
		if phaseName != "" {
			err := recover()
			stack := make([]byte, 16384)
			n := runtime.Stack(stack, false)
			stack = stack[:n]
			if f.HTMLWriter != nil {
				f.HTMLWriter.flushPhases()
			}
			f.Fatalf("panic during %s while compiling %s:\n\n%v\n\n%s\n", phaseName, f.Name, err, stack)
		}
	}()

	// 跑完所有关卡
	if f.Log() {
		printFunc(f)
	}
	f.HTMLWriter.WritePhase("start", "start")
	if BuildDump != "" && BuildDump == f.Name {
		f.dumpFile("build")
	}
	if checkEnabled {
		checkFunc(f)
	}
	const logMemStats = false
	for _, p := range passes {
		if !f.Config.optimize && !p.required || p.disabled {
			continue
		}
		f.pass = &p
		phaseName = p.name
		if f.Log() {
			f.Logf("  pass %s begin\n", p.name)
		}
		// TODO:在此过程中捕获日志，将其添加到HTML
		var mStart runtime.MemStats
		if logMemStats || p.mem {
			runtime.ReadMemStats(&mStart)
		}

		if checkEnabled && !f.scheduled {
			// 通过随机化测试我们是否不依赖于值顺序
			// 每个块中值的顺序。见第18169期。
			for _, b := range f.Blocks {
				for i := 0; i < len(b.Values)-1; i++ {
					j := i + rnd.Intn(len(b.Values)-i)
					b.Values[i], b.Values[j] = b.Values[j], b.Values[i]
				}
			}
		}

		tStart := time.Now()
		p.fn(f)
		tEnd := time.Now()

		// 需要比“记录整个中间结果”更简单的东西。
		if f.Log() || f.HTMLWriter != nil {
			time := tEnd.Sub(tStart).Nanoseconds()
			var stats string
			if logMemStats {
				var mEnd runtime.MemStats
				runtime.ReadMemStats(&mEnd)
				nBytes := mEnd.TotalAlloc - mStart.TotalAlloc
				nAllocs := mEnd.Mallocs - mStart.Mallocs
				stats = fmt.Sprintf("[%d ns %d allocs %d bytes]", time, nAllocs, nBytes)
			} else {
				stats = fmt.Sprintf("[%d ns]", time)
			}

			if f.Log() {
				f.Logf("  pass %s end %s\n", p.name, stats)
				printFunc(f)
			}
			f.HTMLWriter.WritePhase(phaseName, fmt.Sprintf("%s <span class=\"stats\">%s</span>", phaseName, stats))
		}
		if p.time || p.mem {
			// 具有足够上下文的环绕计时信息，以便进行比较。
			time := tEnd.Sub(tStart).Nanoseconds()
			if p.time {
				f.LogStat("TIME(ns)", time)
			}
			if p.mem {
				var mEnd runtime.MemStats
				runtime.ReadMemStats(&mEnd)
				nBytes := mEnd.TotalAlloc - mStart.TotalAlloc
				nAllocs := mEnd.Mallocs - mStart.Mallocs
				f.LogStat("TIME(ns):BYTES:ALLOCS", time, nBytes, nAllocs)
			}
		}
		if p.dump != nil && p.dump[f.Name] {
			// 将函数转储到适当命名的文件
			f.dumpFile(phaseName)
		}
		if checkEnabled {
			checkFunc(f)
		}
	}

	if f.HTMLWriter != nil {
		// 确保我们将任何挂起的阶段写入html
		f.HTMLWriter.flushPhases()
	}

	if f.ruleMatches != nil {
		var keys []string
		for key := range f.ruleMatches {
			keys = append(keys, key)
		}
		sort.Strings(keys)
		buf := new(bytes.Buffer)
		fmt.Fprintf(buf, "%s: ", f.Name)
		for _, key := range keys {
			fmt.Fprintf(buf, "%s=%d ", key, f.ruleMatches[key])
		}
		fmt.Fprint(buf, "\n")
		fmt.Print(buf.String())
	}

	// 挤压错误打印延迟
	phaseName = ""
}

// dumpFile根据阶段名和函数名创建一个文件
// 转储是对文件进行的，以避免在转储之前缓冲巨大的字符串
// 输出
func (f *Func) dumpFile(phaseName string) {
	f.dumpFileSeq++
	fname := fmt.Sprintf("%s_%02d__%s.dump", f.Name, int(f.dumpFileSeq), phaseName)
	fname = strings.Replace(fname, " ", "_", -1)
	fname = strings.Replace(fname, "/", "_", -1)
	fname = strings.Replace(fname, ":", "_", -1)

	fi, err := os.Create(fname)
	if err != nil {
		f.Warnl(src.NoXPos, "Unable to create after-phase dump file %s", fname)
		return
	}

	p := stringFuncPrinter{w: fi}
	fprintFunc(p, f)
	fi.Close()
}

type pass struct {
	name     string
	fn       func(*Func)
	required bool
	disabled bool
	time     bool            // 报告运行时间通行证
	mem      bool            // 报告mem统计数据以运行pass
	stats    int             // 传递报告自身的“统计信息”（例如，已删除的分支）
	debug    int             // pass执行一些调试=1应为错误测试友好的Warnl格式。
	test     int             // 通过特定的特别选项，可能对开发有用
	dump     map[string]bool // 如果函数名匹配，则转储
}

func (p *pass) addDump(s string) {
	if p.dump == nil {
		p.dump = make(map[string]bool)
	}
	p.dump[s] = true
}

func (p *pass) String() string {
	if p == nil {
		return "nil pass"
	}
	return p.name
}

// 在每个阶段之间运行一致性检查程序
var (
	checkEnabled  = false
	checkRandSeed = 0
)

// 调试输出
var IntrinsicsDebug int
var IntrinsicsDisable bool

var BuildDebug int
var BuildTest int
var BuildStats int
var BuildDump string // ssa初始生成后要转储的函数的名称

// PhaseOption在指定ssa阶段设置指定标志，
// 如果此操作成功，则返回空字符串，或者返回一个字符串
// 如果不是，则返回错误。
// 还将检查阶段名称的版本是否匹配，并将其替换为“”。
// 如果阶段名称以“~”开头，则其余下划线将替换为空格
// 版本用作正则表达式以匹配阶段名称。
// None
// 已证明有用的特殊情况：
// ssa/check/on启用每个阶段后的检查
// ssa/all/time启用所有阶段的时间报告
// None
// 请参阅gc/lex.go以了解选项字符串的剖析。
// 示例使用：
// None
// GO_GCFLAGS=-d=ssa/generic_cse/time，ssa/generic_cse/stats，ssa/generic_cse/debug=3./make.bash
// None
// BOOT_GO_GCFLAGS=-d='ssa/~^.*scc$/off'GO_GCFLAGS='-d=ssa/~^.*scc$/off./make.bash
// None
func PhaseOption(phase, flag string, val int, valString string) string {
	switch phase {
	case "", "help":
		lastcr := 0
		phasenames := "    check, all, build, intrinsics"
		for _, p := range passes {
			pn := strings.Replace(p.name, " ", "_", -1)
			if len(pn)+len(phasenames)-lastcr > 70 {
				phasenames += "\n    "
				lastcr = len(phasenames)
				phasenames += pn
			} else {
				phasenames += ", " + pn
			}
		}
		return `PhaseOptions usage:

    go tool compile -d=ssa/<phase>/<flag>[=<value>|<function_name>]

where:

- <phase> is one of:
` + phasenames + `

- <flag> is one of:
    on, off, debug, mem, time, test, stats, dump, seed

- <value> defaults to 1

- <function_name> is required for the "dump" flag, and specifies the
  name of function to dump after <phase>

Phase "all" supports flags "time", "mem", and "dump".
Phase "intrinsics" supports flags "on", "off", and "debug".

If the "dump" flag is specified, the output is written on a file named
<phase>__<function_name>_<seq>.dump; otherwise it is directed to stdout.

Examples:

    -d=ssa/check/on
enables checking after each phase

	-d=ssa/check/seed=1234
enables checking after each phase, using 1234 to seed the PRNG
used for value order randomization

    -d=ssa/all/time
enables time reporting for all phases

    -d=ssa/prove/debug=2
sets debugging level to 2 in the prove pass

Be aware that when "/debug=X" is applied to a pass, some passes
will emit debug output for all functions, and other passes will
only emit debug output for functions that match the current
GOSSAFUNC value.

Multiple flags can be passed at once, by separating them with
commas. For example:

    -d=ssa/check/on,ssa/all/time
`
	}

	if phase == "check" {
		switch flag {
		case "on":
			checkEnabled = val != 0
			debugPoset = checkEnabled // 还可以在prove的数据结构中启用高级自检
			return ""
		case "off":
			checkEnabled = val == 0
			debugPoset = checkEnabled
			return ""
		case "seed":
			checkEnabled = true
			checkRandSeed = val
			debugPoset = checkEnabled
			return ""
		}
	}

	alltime := false
	allmem := false
	alldump := false
	if phase == "all" {
		switch flag {
		case "time":
			alltime = val != 0
		case "mem":
			allmem = val != 0
		case "dump":
			alldump = val != 0
			if alldump {
				BuildDump = valString
			}
		default:
			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
		}
	}

	if phase == "intrinsics" {
		switch flag {
		case "on":
			IntrinsicsDisable = val == 0
		case "off":
			IntrinsicsDisable = val != 0
		case "debug":
			IntrinsicsDebug = val
		default:
			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
		}
		return ""
	}
	if phase == "build" {
		switch flag {
		case "debug":
			BuildDebug = val
		case "test":
			BuildTest = val
		case "stats":
			BuildStats = val
		case "dump":
			BuildDump = valString
		default:
			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
		}
		return ""
	}

	underphase := strings.Replace(phase, "_", " ", -1)
	var re *regexp.Regexp
	if phase[0] == '~' {
		r, ok := regexp.Compile(underphase[1:])
		if ok != nil {
			return fmt.Sprintf("Error %s in regexp for phase %s, flag %s", ok.Error(), phase, flag)
		}
		re = r
	}
	matchedOne := false
	for i, p := range passes {
		if phase == "all" {
			p.time = alltime
			p.mem = allmem
			if alldump {
				p.addDump(valString)
			}
			passes[i] = p
			matchedOne = true
		} else if p.name == phase || p.name == underphase || re != nil && re.MatchString(p.name) {
			switch flag {
			case "on":
				p.disabled = val == 0
			case "off":
				p.disabled = val != 0
			case "time":
				p.time = val != 0
			case "mem":
				p.mem = val != 0
			case "debug":
				p.debug = val
			case "stats":
				p.stats = val
			case "test":
				p.test = val
			case "dump":
				p.addDump(valString)
			default:
				return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
			}
			if p.disabled && p.required {
				return fmt.Sprintf("Cannot disable required SSA phase %s using -d=ssa/%s debug option", phase, phase)
			}
			passes[i] = p
			matchedOne = true
		}
	}
	if matchedOne {
		return ""
	}
	return fmt.Sprintf("Did not find a phase matching %s in -d=ssa/... debug option", phase)
}

// 编译器的过程列表
var passes = [...]pass{
	// TODO:将phielim和copyelim合并为一个过程？
	{name: "number lines", fn: numberLines, required: true},
	{name: "early phielim", fn: phielim},
	{name: "early copyelim", fn: copyelim},
	{name: "early deadcode", fn: deadcode}, // 删除生成的死代码，以避免在opt期间执行无意义的工作
	{name: "short circuit", fn: shortcircuit},
	{name: "decompose user", fn: decomposeUser, required: true},
	{name: "pre-opt deadcode", fn: deadcode},
	{name: "opt", fn: opt, required: true},               // 注意：一些通用规则知道选择通行证的名称。TODO:拆分所需规则并优化规则
	{name: "zero arg cse", fn: zcse, required: true},     // 需要合并OpSB值
	{name: "opt deadcode", fn: deadcode, required: true}, // 删除opt期间孤立的所有块
	{name: "generic cse", fn: cse},
	{name: "phiopt", fn: phiopt},
	{name: "gcse deadcode", fn: deadcode, required: true}, // cse和phiopt后的清理
	{name: "nilcheckelim", fn: nilcheckelim},
	{name: "prove", fn: prove},
	{name: "early fuse", fn: fuseEarly},
	{name: "decompose builtin", fn: decomposeBuiltIn, required: true},
	{name: "expand calls", fn: expandCalls, required: true},
	{name: "softfloat", fn: softfloat, required: true},
	{name: "late opt", fn: opt, required: true}, // TODO:拆分所需规则并优化规则
	{name: "dead auto elim", fn: elimDeadAutosGeneric},
	{name: "generic deadcode", fn: deadcode, required: true}, // 移除死掉的店铺，否则会弄乱连锁店
	{name: "check bce", fn: checkbce},
	{name: "branchelim", fn: branchelim},
	{name: "late fuse", fn: fuseLate},
	{name: "dse", fn: dse},
	{name: "writebarrier", fn: writebarrier, required: true}, // 展开写屏障操作
	{name: "insert resched checks", fn: insertLoopReschedChecks,
		disabled: !buildcfg.Experiment.PreemptibleLoops}, // 在循环中插入重新调整的检查。
	{name: "lower", fn: lower, required: true},
	{name: "addressing modes", fn: addressingModes, required: false},
	{name: "lowered deadcode for cse", fn: deadcode}, // 紧靠CSE之前的死代码避免了CSE再次激活死值
	{name: "lowered cse", fn: cse},
	{name: "elim unread autos", fn: elimUnreadAutos},
	{name: "tighten tuple selectors", fn: tightenTupleSelectors, required: true},
	{name: "lowered deadcode", fn: deadcode, required: true},
	{name: "checkLower", fn: checkLower, required: true},
	{name: "late phielim", fn: phielim},
	{name: "late copyelim", fn: copyelim},
	{name: "tighten", fn: tighten}, // 使值更接近其用途
	{name: "late deadcode", fn: deadcode},
	{name: "critical", fn: critical, required: true}, // 删除关键边
	{name: "phi tighten", fn: phiTighten},            // 将可重物质化的phi参数放在使用附近，以减少值的使用寿命
	{name: "likelyadjust", fn: likelyadjust},
	{name: "layout", fn: layout, required: true},     // 明细表块
	{name: "schedule", fn: schedule, required: true}, // 明细表值
	{name: "late nilcheck", fn: nilcheckelim2},
	{name: "flagalloc", fn: flagalloc, required: true}, // 分配标志寄存器
	{name: "regalloc", fn: regalloc, required: true},   // 分配整型和浮点型寄存器+堆栈插槽
	{name: "loop rotate", fn: loopRotate},
	{name: "stackframe", fn: stackframe, required: true},
	{name: "trim", fn: trim}, // 清除空块
}

// 仔细检查相位顺序约束。
// 本规范旨在记录订购要求
// 在不同的阶段之间。它不会覆盖过程
// 上面的清单。
type constraint struct {
	a, b string // a必须先到b
}

var passOrder = [...]constraint{
	// “插入重新调整的支票”使用mem，最好先清理商店。
	{"dse", "insert resched checks"},
	// 插入重新调整的检查将添加包含常规指令的新块
	{"insert resched checks", "lower"},
	{"insert resched checks", "tighten"},

	// prove依赖于公共子表达式消除以获得最大效益。
	{"generic cse", "prove"},
	// 验证后的死代码可消除所有新的死块。
	{"prove", "generic deadcode"},
	// 常见的子表达式死前存储elim，以便我们识别
	// 当两个地址表达式相同时。
	{"generic cse", "dse"},
	// cse可显著提高尼切林的疗效
	{"generic cse", "nilcheckelim"},
	// 允许死代码在nilcheckelim之后清除
	{"nilcheckelim", "generic deadcode"},
	// nilcheckelim生成普通基本块序列
	{"nilcheckelim", "late fuse"},
	// nilcheckelim依赖opt重写用户nil检查
	{"opt", "nilcheckelim"},
	// 当尽可能多的值被删除时，拧紧将最有效
	{"generic deadcode", "tighten"},
	{"generic cse", "tighten"},
	// checkbce需要删除这些值
	{"generic deadcode", "check bce"},
	// 在分解内置对象之前不要运行优化过程
	{"decompose builtin", "late opt"},
	// 分解内置是可能引入新浮点运算的最后一步，所以在它之后运行softfloat
	{"decompose builtin", "softfloat"},
	// 元组选择器必须紧靠生成器并在调度之前消除重复
	{"tighten tuple selectors", "schedule"},
	// 在phi拧紧之前移除关键边，以便phi arg得到更好的放置
	{"critical", "phi tighten"},
	// 在删除关键边之前，不要布局块
	{"critical", "layout"},
	// regalloc要求移除所有关键边缘
	{"critical", "regalloc"},
	// regalloc要求调度块中的所有值
	{"schedule", "regalloc"},
	// checkLower必须在降低和后续失效代码elim后运行
	{"lower", "checkLower"},
	{"lowered deadcode", "checkLower"},
	// 延迟检查需要安排指示。
	{"schedule", "late nilcheck"},
	// flagalloc需要安排指令。
	{"schedule", "flagalloc"},
	// regalloc需要首先分配标志。
	{"flagalloc", "regalloc"},
	// loopRotate将混淆regalloc。
	{"regalloc", "loop rotate"},
	// stackframe需要了解溢出的寄存器。
	{"regalloc", "stackframe"},
	// 修剪需要重新进行。
	{"regalloc", "trim"},
}

func init() {
	for _, c := range passOrder {
		a, b := c.a, c.b
		i := -1
		j := -1
		for k, p := range passes {
			if p.name == a {
				i = k
			}
			if p.name == b {
				j = k
			}
		}
		if i < 0 {
			log.Panicf("pass %s not found", a)
		}
		if j < 0 {
			log.Panicf("pass %s not found", b)
		}
		if i >= j {
			log.Panicf("passes %s and %s out of order", a, b)
		}
	}
}
